package apply

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/src/data_structure/list"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/24 00:58
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 **/
type MaxValuePathByRecursion struct {
	MaxValue     int   // 最大的子树路径和
	MaxValuePath []int // 最大的子树路径和的Path
}

func (m *MaxValuePathByRecursion) Method(node *list.Node) int {
	if node == nil {
		return 0
	}
	m.MaxValue = 0
	m.MaxValuePath = make([]int, 0)
	tempArr := make([]int, 0)
	m.roll(node, 0, tempArr)
	return m.MaxValue
}

func (m *MaxValuePathByRecursion) roll(node *list.Node, tempMaxValue int, tempArr []int) {
	if node == nil {
		return
	}
	if tempMaxValue > m.MaxValue {
		m.MaxValue = tempMaxValue
		m.MaxValuePath = make([]int, len(tempArr))
		copy(m.MaxValuePath, tempArr)
	}

	tempMaxValue += node.Value.(int)
	tempArr = append(tempArr, node.Value.(int))
	m.roll(node.Left, tempMaxValue, tempArr)
	m.roll(node.Right, tempMaxValue, tempArr)

	tempMaxValue -= node.Value.(int)
	tempArr = tempArr[:len(tempArr)-1]
	return
}

func (m *MaxValuePathByRecursion) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Tree, C.BackTrack},
		Desc: &C.Desc{
			Name:        "MaxValuePathByRecursion",
			NameCn:      "计算二叉树中最大的子树路径和",
			Description: "",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
			},
		},
	}
}
